package week3.blog_code.exer1003;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt(); // 读取测试数据组数
        while (count > 0) {
            int n = scanner.nextInt(); // 读取每一组测试用例
            // 1. 状态定义：dp[i]表示宽度为3，长度为i的铺设方案数
            int[] dp = new int[n + 1];
            // 2. 状态初始化
            dp[1] = 1;
            dp[2] = 3;
            // 3. 状态转移方程
            for (int i = 3; i <= n; i++) {
                dp[i] = dp[i - 1] + 2 * dp[i - 2];
            }
            // 4. 返回值
            System.out.println(dp[n]);
            count--;
        }
    }
}
